/*
	Copyright (c) 2012 by karmaleaving@qq.com. All rights RESERVED.
*/
#ifndef __STD_MEMORY_H_VERSION_SSTD__
#define __STD_MEMORY_H_VERSION_SSTD__

#include "iterator.hpp"
#include "auto_ptr.hpp" // just include, not used in this file.
#include <string.h>
#include <new>
//extern void *memmove( void *, const void *, size_t);
//extern void *memset( void *, int, size_t);

//#define _SSTD_USE_DEBUG_ALLOCATE_
#define _SSTD_USE_TYPE_TRAITS_
#define _SSTD_USE_NEW_
#define _SSTD_USE_ALLOCATOR_
#define _SSTD_USE_MEM_FUNCTION_

#define REAL_ADDRESS(iterator)  &(*iterator)
#define CONSTRUCT(iterator, exp)  ::new(REAL_ADDRESS(iterator)) exp
#define DESTROY(iterator, value_type)  (iterator)->~value_type()

SSTL_BEGIN

#ifdef _SSTD_USE_TYPE_TRAITS_

// CLASS _type_traits_ {
#define SHORT_TYPE_TRAITS_DEFINE(__trivial_type) \
	typedef __trivial_type trivial_type
#define SHORT_TYPE_TRAITS(__type_name, __trivial_type) \
	template<> struct SSTD::_type_traits_<__type_name> \
{ SHORT_TYPE_TRAITS_DEFINE(__trivial_type); }
// CLASS type category {
struct _trivial_tag_ {};
struct _non_trivial_tag_{};
// CLASS type category }
template<typename Type>
struct _type_traits_
{
	SHORT_TYPE_TRAITS_DEFINE(_non_trivial_tag_);
};
template<typename Type>
struct _type_traits_<Type *>
{
	SHORT_TYPE_TRAITS_DEFINE(_trivial_tag_);
};
SHORT_TYPE_TRAITS(char, _trivial_tag_);
SHORT_TYPE_TRAITS(signed char, _trivial_tag_);
SHORT_TYPE_TRAITS(unsigned char, _trivial_tag_);
SHORT_TYPE_TRAITS(short, _trivial_tag_);
SHORT_TYPE_TRAITS(unsigned short, _trivial_tag_);
SHORT_TYPE_TRAITS(int, _trivial_tag_);
SHORT_TYPE_TRAITS(unsigned int, _trivial_tag_);
SHORT_TYPE_TRAITS(long, _trivial_tag_);
SHORT_TYPE_TRAITS(unsigned long, _trivial_tag_);
SHORT_TYPE_TRAITS(long long, _trivial_tag_);
SHORT_TYPE_TRAITS(unsigned long long, _trivial_tag_);
SHORT_TYPE_TRAITS(float, _trivial_tag_);
SHORT_TYPE_TRAITS(double, _trivial_tag_);
SHORT_TYPE_TRAITS(long double, _trivial_tag_);
// CLASS _type_traits_ }
#endif // _SSTD_USE_TYPE_TRAITS_

#ifdef _SSTD_USE_NEW_
// FUNCTION operator new FUNCTION operator delete {
//inline void * operator new(size_t const & bytes)
//{
//	return ::operator new(bytes);
//}
//inline void operator delete(void *ptr, size_t const &bytes)
//{
//	::operator delete(ptr);
//}
// FUNCTION operator new FUNCTION operator delete }
#endif // _SSTD_USE_NEW_

template<typename Type, typename trivial = typename _type_traits_<Type>::trivial_type>
class _memory_helper_;

#ifdef _SSTD_USE_ALLOCATOR_
#ifdef _SSTD_USE_DEBUG_ALLOCATE_
size_t allocate_bytes = 0;
#endif // _SSTD_USE_DEBUG_ALLOCATE_
// CLASS allocator {
#define _ALLOC_MAX_SIZE_ (1U<<24)
template<typename Type>
class allocator
{
public:
	SSTD_NEST_TYPE_DEFINE(Type);
	template<typename other_t>
	struct rebind{ typedef allocator<other_t> other; };
private:
	static const size_type _max_size = ~(size_type)0 / sizeof(value_type);
public:
	allocator() 
	{}
	allocator(allocator const & o)
	{}
	template<typename Type2>
	allocator(allocator<Type2> const &)
	{}
	~allocator()
	{}
	static pointer address(reference value)
	{
		return &value;
	}
	static const_pointer address(const_reference value)
	{
		return &value;
	}
	static pointer allocate(size_type num, const void * = 0)
	{
#ifdef _SSTD_USE_DEBUG_ALLOCATE_
		allocate_bytes += num * sizeof(Type);
#endif // _SSTD_USE_DEBUG_ALLOCATE_
		void * mem = ::operator new(num * sizeof(Type));
		return static_cast<pointer>(mem);
	}
	static void deallocate(pointer p, size_type num)
	{
#ifdef _SSTD_USE_DEBUG_ALLOCATE_
		allocate_bytes -= num * sizeof(Type);
#endif // _SSTD_USE_DEBUG_ALLOCATE_
		::operator delete (p, num * sizeof(Type));
	}
	static size_type max_size()
	{
		return _max_size;
	}
	template<typename Type2>
	bool operator ==(allocator<Type2> const &) const
	{
		return true;
	}
	template<typename Type2>
	bool operator !=(allocator<Type2> const &) const
	{
		return false;
	}
public: // Below Just for standard.
	static void construct(pointer p, const_reference value) // copy construct
	{
		new(p) Type(value);
	}
	static void destroy(pointer p)
	{
		SSTD::_memory_helper_<value_type>::destroy(p);
	}
};
// CLASS allocator }
// CLASS _memory_helper_ {
template<typename Type>
class _memory_helper_<Type, _trivial_tag_>
{
public:
	SSTD_NEST_TYPE_DEFINE(Type);
	template<typename FwdIter, typename Value>
	static void raw_fill(FwdIter dest, Value const &value)
	{
		CONSTRUCT(dest, value_type(value));
	}
	template<typename InIter, typename FwdIter>
	static void raw_copy(InIter first, FwdIter dest)
	{
		CONSTRUCT(dest, value_type(*first));
	}
	template<typename FwdIter>
	static void initialize(FwdIter iter)
	{
	}
	template<typename InIter>
	static void destroy(InIter)
	{ // do nothing.
	}
	template<typename FwdIter>
	static void destroy(FwdIter first, FwdIter last)
	{ // do nothing.
	}
	template<class InIter, class FwdIter>
	static void raw_copy(InIter first, InIter last, FwdIter dest)
	{
		for(; first != last; ++first, ++dest) 
			CONSTRUCT(dest, value_type(*first));
	}
	static void raw_copy(const_pointer first,
		const_pointer last, pointer dest)
	{
		::memmove(dest, first, (last - first) * sizeof(value_type));
	}
	static void raw_copy(pointer first,
		pointer last, pointer dest)
	{
		::memmove(dest, first, (last - first) * sizeof(value_type));
	}
	template<class FwdIter, class Value>
	static void raw_fill(FwdIter dest, FwdIter out_last, const Value &value)
	{
		for(; dest != out_last; ++dest)
			CONSTRUCT(dest, value_type(value));
	}
	static void raw_fill(pointer dest,
		pointer out_last, value_type const &value)
	{
		size_type num = out_last - dest;
		if(num == 1) 
			CONSTRUCT(dest, value_type(value));
		else if(sizeof(value_type) == 1)
		{
			::memset(dest, *(char*)(&value), out_last - dest);
		}
		else// Any o way?
		{
			for(; dest != out_last; ++dest) *dest = value;
		}
	}
	template<class BidIter>
	static void raw_move_backward(BidIter first, BidIter last, BidIter first_dest)
	{
		SSTD::advance(first_dest, SSTD::distance(first, last));
		for(; last != first; )
		{
			CONSTRUCT(--first_dest, value_type(*--last));
		}
	}
	static void raw_move_backward(const_pointer first, const_pointer last, pointer first_dest)
	{
		::memmove(first_dest, first, (last - first) * sizeof(value_type));
	}
	static void raw_move_backward(pointer first, pointer last, pointer first_dest)
	{
		::memmove(first_dest, first, (last - first) * sizeof(value_type));
	}
	template<class FwdIter>
	static void raw_move_forward(FwdIter first, FwdIter last, FwdIter dest)
	{
		for(; first != last; ++first, ++dest)
			CONSTRUCT(dest, value_type(*first));
	}
	static void raw_move_forward(const_pointer first, const_pointer last, pointer dest)
	{
		::memmove(dest, first, (last - first) * sizeof(value_type));
	}
	static void raw_move_forward(pointer first, pointer last, pointer dest)
	{
		::memmove(dest, first, (last - first) * sizeof(value_type));
	}
	// do with num.
	template<typename FwdIter>
	static void destroy_n(FwdIter first, size_type num)
	{ // do nothing.
	}
	template<class InIter, class FwdIter>
	static void raw_copy_n(InIter first, size_type num, FwdIter dest)
	{
		for(; num > 0; ++first, ++dest, --num)
			CONSTRUCT(dest, value_type(*first));
	}
	static void raw_copy_n(const_pointer first,
		size_type num, pointer dest)
	{
		::memmove(dest, first, num * sizeof(value_type));
	}
	static void raw_copy_n(pointer first,
		size_type num, pointer dest)
	{
		if(num == 1) CONSTRUCT(dest, value_type(*first));
		else ::memmove(dest, first, num * sizeof(value_type));
	}
	template<class FwdIter>
	static void raw_fill_n(FwdIter dest, size_type num, const_reference value)
	{
		for(; num--; ++dest) 
			CONSTRUCT(dest, value_type(value));
	}
	static void raw_fill_n(pointer dest,
		size_type num, const_reference value)
	{
		if(num == 1) CONSTRUCT(dest, value_type(value));
		else if(sizeof(value_type) == 1)
		{ // spcialize for char, unsigned char, or o whoes value_type is 1 byte.
			::memset(dest, *(char*)(&value), num);
		}
		else
		{ // Any o way?
			for(; num--; ++dest) 
				CONSTRUCT(dest, value_type(value));
		}
	}
	template<class BidIter>
	static void raw_move_backward_n(BidIter first, size_type num, BidIter first_dest)
	{
		SSTD::advance(first_dest, num);
		SSTD::advance(first, num);
		for(; num--; )
		{
			CONSTRUCT(--first_dest, value_type(*--first));
		}
	}
	static void raw_move_backward_n(const_pointer first, size_type num, pointer first_dest)
	{
		::memmove(first_dest, first, num * sizeof(value_type));
	}
	static void raw_move_backward_n(pointer first, size_type num, pointer first_dest)
	{
		::memmove(first_dest, first, num * sizeof(value_type));
	}	
	template<class FwdIter>
	static void raw_move_forward_n(FwdIter first, size_type num, FwdIter dest)
	{
		for(; num--; ++first, ++dest)
			CONSTRUCT(dest, value_type(*first));
	}
	static void raw_move_forward_n(const_pointer first, size_type num, pointer dest)
	{
		::memmove(dest, first, num * sizeof(value_type));
	}
	static void raw_move_forward_n(pointer first, size_type num, pointer dest)
	{
		::memmove(dest, first, num * sizeof(value_type));
	}
	template<typename FwdIter>
	static void initialize(FwdIter first, FwdIter last)
	{
	}
	template<typename FwdIter>
	static void initialize_n(FwdIter first, size_t num)
	{
	}
	// initialized {
	template<class InIter, class OutIter>
	static OutIter copy(InIter first, InIter last, OutIter dest)
	{
		for(; first != last; ++dest, ++first) *dest = *first;
		return dest;
	}
	static pointer copy(const_pointer first, const_pointer last, pointer dest)
	{
		diff_type num = SSTD::distance(first, last);
		::memmove(dest, first, num * sizeof(value_type));
		return dest + num;
	}
	static pointer copy(pointer first, pointer last, pointer dest)
	{
		diff_type num = SSTD::distance(first, last);
		::memmove(dest, first, num * sizeof(value_type));
		return dest + num;
	}
	template<class InIter, class OutIter>
	static OutIter copy_n(InIter first, size_type num, OutIter dest)
	{
		for(;num--; ++dest, ++first) *dest = *first;
		return dest;
	}
	static pointer copy_n(const_pointer first, size_type num, pointer dest)
	{
		::memmove(dest, first, num * sizeof(value_type));
		return dest + num;
	}
	static pointer copy_n(pointer first, size_type num, pointer dest)
	{
		::memmove(dest, first, num * sizeof(value_type));
		return dest + num;
	}
	template<class InIter, class OutIter>
	static OutIter copy_backward(InIter first, InIter last,
		OutIter last_dest)
	{
		while(first != last)
		{
			--last_dest, --last;
			*last_dest = *last;
		}
		return last_dest;
	}
	static pointer copy_backward(const_pointer first, const_pointer last, pointer last_dest)
	{
		ASSERT_REPAIR(first <= last, return last_dest);
		size_t num = SSTD::distance(first, last);
		last_dest -= num;
		::memmove(last_dest, first, num * sizeof(value_type));
		return last_dest;
	}
	static pointer copy_backward(pointer first, pointer last, pointer last_dest)
	{
		ASSERT_REPAIR(first <= last, return last_dest);
		size_t num = SSTD::distance(first, last);
		last_dest -= num;
		::memmove(last_dest, first, num * sizeof(value_type));
		return last_dest;
	}
	// initialized }
};
template<typename Type>
class _memory_helper_<Type, _non_trivial_tag_> 
{
public:
	SSTD_NEST_TYPE_DEFINE(Type);
	template<typename FwdIter, typename Value>
	static void raw_fill(FwdIter dest, Value const &value)
	{
		CONSTRUCT(dest, value_type(value));
	}
	template<typename InIter, typename FwdIter>
	static void raw_copy(InIter first, FwdIter dest)
	{
		CONSTRUCT(dest, value_type(*first));
	}
	template<typename FwdIter>
	static void initialize(FwdIter iter)
	{
		CONSTRUCT(iter, value_type());
	}
	template<typename FwdIter>
	static void destroy(FwdIter iter)
	{
		DESTROY(iter, value_type);
	}
	template<typename FwdIter>
	static void destroy(FwdIter first, FwdIter last)
	{
		for(; first != last; ++first) 
			DESTROY(first, value_type);
	}
	template<class InIter, class FwdIter>
	static void raw_copy(InIter first, InIter last, FwdIter dest)
	{
		for(; first != last; ++first, ++dest)
			CONSTRUCT(REAL_ADDRESS(dest), value_type(*first));
	}
	template<class FwdIter>
	static void raw_fill(FwdIter dest, FwdIter out_last, const_reference value)
	{
		for(; dest != out_last; ++dest)
			CONSTRUCT(REAL_ADDRESS(dest), value_type(value));
	}
	template<class BidIter>
	static void raw_move_backward(BidIter first, BidIter last, BidIter first_dest)
	{
		SSTD::advance(first_dest, SSTD::distance(first, last));
		for(; last != first; ) 
		{
			--first_dest, --last;
			CONSTRUCT(REAL_ADDRESS(first_dest), value_type(*last));
			DESTROY(last, value_type);
		}
	}
	template<class FwdIter>
	static void raw_move_forward(FwdIter first, FwdIter last, FwdIter first_dest)
	{
		for(; first != last; ++first, ++first_dest)
		{
			CONSTRUCT(REAL_ADDRESS(first_dest), value_type(*first));
			DESTROY(first, value_type);
		}
	}
	// do with num.
	template<typename FwdIter>
	static void destroy_n(FwdIter first, size_type num)
	{
		for(; num--; ++first) 
			DESTROY(first, value_type);
	}
	template<class InIter, class FwdIter>
	static void raw_copy_n(InIter first, size_type num, FwdIter dest)
	{
		for(; num--; ++first, ++dest) 
			CONSTRUCT(REAL_ADDRESS(dest), value_type(*first));
	}
	template<class FwdIter>
	static void raw_fill_n(FwdIter dest, size_type num, const_reference value)
	{
		for(; num--; ++dest) 
			CONSTRUCT(REAL_ADDRESS(dest), value_type(value));
	}
	template<class BidIter>
	static void raw_move_backward_n(BidIter first, size_type num, BidIter first_dest)
	{
		SSTD::advance(first_dest, num);
		SSTD::advance(first, num);
		for(; num--; ) 
		{
			--first_dest, --first;
			CONSTRUCT(REAL_ADDRESS(first_dest), value_type(*first));
			DESTROY(first, value_type);
		}
	}
	template<class FwdIter>
	static void raw_move_forward_n(FwdIter first, size_type num, FwdIter dest)
	{
		for(; num--; ++first, ++dest)
		{
			CONSTRUCT(REAL_ADDRESS(dest), value_type(*first));
			DESTROY(first, value_type);
		}
	}
	template<typename FwdIter>
	static void initialize(FwdIter first, FwdIter last)
	{
		raw_fill(first, last, value_type());
	}
	template<typename FwdIter>
	static void initialize_n(FwdIter first, size_type num)
	{
		raw_fill_n(first, num, value_type());
	}
	// initialized {
	template<class InIter, class OutIter>
	static OutIter copy(InIter first, InIter last, OutIter dest)
	{
		while(first != last)
		{
			*dest = *first;
			++dest, ++first;
		}
		return dest;
	}
	template<class InIter, class OutIter>
	static OutIter copy_n(InIter first, size_type num, OutIter dest)
	{
		while(num--)
		{
			*dest = *first;
			++dest, ++first;
		}
		return dest;
	}
	template<class InIter, class OutIter>
	static OutIter copy_backward(InIter first, InIter last,
		OutIter last_dest)
	{
		while(first != last)
		{
			--last_dest, --last;
			*last_dest = *last;
		}
		return last_dest;
	}
	// initialized }
};
// CLASS _memory_helper_ }
#endif // _SSTD_USE_ALLOCATOR_

#ifdef _SSTD_USE_MEM_FUNCTION_
template<typename value_type>
inline value_type * allocate_buffer(size_t num)
{
	return static_cast<value_type*>(::operator new(num * sizeof(value_type)));
}
template<typename value_type>
inline void deallocate_buffer(value_type *buffer, size_t num)
{
	::operator delete(buffer, num * sizeof(value_type));
}
// FUNCTION construct destroy uninitialized_copy uninitialized_fill ... {
template<typename value_type, class Type1>
inline void construct(value_type * ptr, Type1 const &value)
{
	SSTD::_memory_helper_<value_type>::construct(ptr, value);
}
template<typename value_type>
inline void destroy(value_type *ptr)
{
	SSTD::_memory_helper_<value_type>::destroy(ptr);
}
template<class FwdIter>
inline void destroy(FwdIter first, FwdIter last)
{
	SSTD::_memory_helper_<typename iterator_traits<FwdIter>::value_type>::
		destroy(first, last);
}
template<class FwdIter>
inline void destroy_n(FwdIter first, size_t num)
{
	SSTD::_memory_helper_<typename iterator_traits<FwdIter>::value_type>::
		destroy_n(first, num);
}
template<class InIter, class FwdIter>
inline void uninitialized_copy(InIter first, InIter last, FwdIter result)
{
	SSTD::_memory_helper_<typename iterator_traits<FwdIter>::value_type>::
		uninitialized_copy(first, last, result);
}
template<class InIter, class FwdIter>
inline void uninitialized_copy_n(InIter first, size_t num, FwdIter result)
{
	SSTD::_memory_helper_<typename iterator_traits<FwdIter>::value_type>::
		uninitialized_copy_n(first, num, result);
}
template<class FwdIter, typename Type1>
inline void uninitialized_fill(FwdIter first, FwdIter last, Type1 const &value)
{
	SSTD::_memory_helper_<typename iterator_traits<FwdIter>::value_type>::
		uninitialized_fill(first, last, value);
}
template<class FwdIter, typename Type1>
inline void uninitialized_fill_n(FwdIter first, size_t num, Type1 const &value)
{
	SSTD::_memory_helper_<typename iterator_traits<FwdIter>::value_type>::
		uninitialized_fill_n(first, num, value);
}
// FUNCTION construct destroy uninitialized_copy uninitialized_fill ... }
#endif // _SSTD_USE_MEM_FUNCTION_
SSTL_END
#endif // __STD_MEMORY_H_VERSION_SSTD__

